package com.zyk.leetcode;

import java.util.HashSet;

/**
 * @author zhangsan
 * @date 2021/4/6 17:49
 */
public class C3 {

    // https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
    // 滑动窗口解
    // l r 两个指针
    // 判重使用set
    // 不断地扩大窗口范围, 直到遇到重复字符的时候.计算一下答案, 然后移除掉第一个字符
    // l ~ (r-1) 没有重复元素那么 (l+1) ~ (r-1) 也没有重复元素
    // 所以时间复杂度O(N)
    public static int lengthOfLongestSubstring(String s) {
        char[] str = s.toCharArray();
        int l = 0, r = -1, ans = 0;
        HashSet<Character> set = new HashSet<>();
        for (; l < str.length; l++) {
            if (l > 0) {
                set.remove(str[l - 1]);
            }
            while (r + 1 < str.length && !set.contains(str[r + 1])) {
                set.add(str[r + 1]);
                r++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }

    // 对数器方法, 暴力解
    public static int compareM(String s) {
        if (s.length() < 2) {
            return s.length();
        }
        char[] str = s.toCharArray();
        int max = 0;
        int j;
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < str.length; i++) {
            set.add(str[i]);
            for (j = i + 1; j < str.length; j++) {
                if (set.contains(str[j])) {
                    set.clear();
                    break;
                }
                set.add(str[j]);
            }
            max = Math.max(max, (j - i));
        }
        return max;
    }


    // for test
    public static void main(String[] args) {
        String str = "abcabcbb";

        System.out.println(compareM(str));
        System.out.println(lengthOfLongestSubstring(str));
    }

}
